<html><head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta content="text/javascript" http-equiv="content-script-type">
<title>tango.util.collection.impl.RBCell</title>

<link rel="stylesheet" type="text/css" href="css/style.css">
<!--[if lt IE 7]><link rel="stylesheet" type="text/css" href="css/ie56hack.css"><![endif]-->
<script language="JavaScript" src="js/util.js" type="text/javascript"></script>
<script language="JavaScript" src="js/tree.js" type="text/javascript"></script>
<script language="JavaScript" src="js/explorer.js" type="text/javascript"></script>
<script>
function anchorFromTitle(title, path, ext) {
  var url = path + title + "." + ext;
  document.write("<a href='" + url + "'>" + title + "</a>");
  }
</script>
</head><body>
<div id="tabarea"></div><div id="explorerclient"></div>
<div id="content"><script>explorer.initialize("tango.util.collection.impl.RBCell");</script>
        <table class="content">
                <tr><td id="docbody"><h1><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791">tango.util.collection.impl.RBCell</a></h1>
                
<dl>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>class <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L41">RBCell</a></span>
<script>explorer.outline.addDecl('RBCell');</script>(T) : Cell!(T);</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">RBCell implements basic capabilities of Red-Black trees,
 an efficient kind of balanced binary tree. The particular
 algorithms used are adaptations of those in Corman,
 Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>.
 This class was inspired by &#40;and code cross-checked with&#41; a 
 similar class by Chuck McManis. The implementations of
 rebalancings during insertion and deletion are
 a little trickier than those versions since they
 don't swap Cell contents or use special dummy nilnodes. 
 <P>
 It is a pure implementation class. For harnesses, see:
 </font><br><br>
<b>See Also:</b><br>
RBTree<br><br>
<b>Authors:</b><br>
Doug Lea<br><br>
<dl>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>bool <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L50">color_</a></span>
<script>explorer.outline.addDecl('color_');</script>; [package]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">The node color &#40;RED, BLACK&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L56">left_</a></span>
<script>explorer.outline.addDecl('left_');</script>; [package]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Pointer to left child
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L62">right_</a></span>
<script>explorer.outline.addDecl('right_');</script>; [package]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Pointer to right child
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L68">parent_</a></span>
<script>explorer.outline.addDecl('parent_');</script>; [private]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Pointer to parent &#40;null if root&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li><span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L75">this</a></span>
<script>explorer.outline.addDecl('this');</script>(T <span class="funcparam">element</span>); [public]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Make a new Cell with given element, null links, and BLACK color.
 Normally only called to establish a new root.
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L90">duplicate</a></span>
<script>explorer.outline.addDecl('duplicate');</script>(); [protected]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return a new RBCell with same element and color as self,
 but with null links. &#40;Since it is never OK to have
 multiple identical links in a RB tree.&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L102">left</a></span>
<script>explorer.outline.addDecl('left');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return left child &#40;or null&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L111">right</a></span>
<script>explorer.outline.addDecl('right');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return right child &#40;or null&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L119">parent</a></span>
<script>explorer.outline.addDecl('parent');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return parent &#40;or null&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>void <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L128">checkImplementation</a></span>
<script>explorer.outline.addDecl('checkImplementation');</script>(); [public]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<b>See Also:</b><br>
tango.util.collection.model.View.View.checkImplementation.<br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L165">leftmost</a></span>
<script>explorer.outline.addDecl('leftmost');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the minimum element of the current &#40;sub&#41;tree
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L176">rightmost</a></span>
<script>explorer.outline.addDecl('rightmost');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the maximum element of the current &#40;sub&#41;tree
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L187">root</a></span>
<script>explorer.outline.addDecl('root');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the root &#40;parentless node&#41; of the tree
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>bool <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L199">isRoot</a></span>
<script>explorer.outline.addDecl('isRoot');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return true if node is a root &#40;i.e., has a null parent&#41;
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L209">successor</a></span>
<script>explorer.outline.addDecl('successor');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the inorder successor, or null if no such
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L230">predecessor</a></span>
<script>explorer.outline.addDecl('predecessor');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the inorder predecessor, or null if no such
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>int <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L250">size</a></span>
<script>explorer.outline.addDecl('size');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return the number of nodes in the subtree
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L267">find</a></span>
<script>explorer.outline.addDecl('find');</script>(T <span class="funcparam">element</span>, Comparator!(T) <span class="funcparam">cmp</span>); [public]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return node of current subtree containing element as element&#40;&#41;, 
 if it exists, else null. 
 Uses Comparator cmp to find and to check equality.
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>int <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L291">count</a></span>
<script>explorer.outline.addDecl('count');</script>(T <span class="funcparam">element</span>, Comparator!(T) <span class="funcparam">cmp</span>); [public]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return number of nodes of current subtree containing element.
 Uses Comparator cmp to find and to check equality.
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L328">copyTree</a></span>
<script>explorer.outline.addDecl('copyTree');</script>(); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return a new subtree containing each element of current subtree
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L360">insertLeft</a></span>
<script>explorer.outline.addDecl('insertLeft');</script>(RBCell <span class="funcparam">Cell</span>, RBCell <span class="funcparam">root</span>); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">There's no generic element insertion. Instead find the
 place you want to add a node and then invoke insertLeft
 or insertRight.
 <P>
 Insert Cell as the left child of current node, and then
 rebalance the tree it is in.
 @param Cell the Cell to add
 @param root, the root of the current tree
 </font><br><br>
<b>Returns:</b><br>
the new root of the current tree. &#40;Rebalancing
 can change the root!&#41;<br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L376">insertRight</a></span>
<script>explorer.outline.addDecl('insertRight');</script>(RBCell <span class="funcparam">Cell</span>, RBCell <span class="funcparam">root</span>); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Insert Cell as the right child of current node, and then
 rebalance the tree it is in.
 @param Cell the Cell to add
 @param root, the root of the current tree
 </font><br><br>
<b>Returns:</b><br>
the new root of the current tree. &#40;Rebalancing
 can change the root!&#41;<br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L392">remove</a></span>
<script>explorer.outline.addDecl('remove');</script>(RBCell <span class="funcparam">root</span>); [public, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Delete the current node, and then rebalance the tree it is in
 @param root the root of the current tree
 </font><br><br>
<b>Returns:</b><br>
the new root of the current tree. &#40;Rebalancing
 can change the root!&#41;<br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L466">swapPosition</a></span>
<script>explorer.outline.addDecl('swapPosition');</script>(RBCell <span class="funcparam">x</span>, RBCell <span class="funcparam">y</span>, RBCell <span class="funcparam">root</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Swap the linkages of two nodes in a tree.
 Return new root, in case it changed.
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>bool <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L594">colorOf</a></span>
<script>explorer.outline.addDecl('colorOf');</script>(RBCell <span class="funcparam">p</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Return color of node p, or BLACK if p is null
 &#40;In the CLR version, they use
 a special dummy `nil' node for such purposes, but that doesn't
 work well here, since it could lead to creating one such special
 node per real node.&#41;</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L602">parentOf</a></span>
<script>explorer.outline.addDecl('parentOf');</script>(RBCell <span class="funcparam">p</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">return parent of node p, or null if p is null
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>void <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L611">setColor</a></span>
<script>explorer.outline.addDecl('setColor');</script>(RBCell <span class="funcparam">p</span>, bool <span class="funcparam">c</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">Set the color of node p, or do nothing if p is null
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L621">leftOf</a></span>
<script>explorer.outline.addDecl('leftOf');</script>(RBCell <span class="funcparam">p</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">return left child of node p, or null if p is null
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L630">rightOf</a></span>
<script>explorer.outline.addDecl('rightOf');</script>(RBCell <span class="funcparam">p</span>); [static, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">return right child of node p, or null if p is null
</font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L637">rotateLeft</a></span>
<script>explorer.outline.addDecl('rotateLeft');</script>(RBCell <span class="funcparam">root</span>); [protected, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">From CLR </font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L657">rotateRight</a></span>
<script>explorer.outline.addDecl('rotateRight');</script>(RBCell <span class="funcparam">root</span>); [protected, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">From CLR </font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L678">fixAfterInsertion</a></span>
<script>explorer.outline.addDecl('fixAfterInsertion');</script>(RBCell <span class="funcparam">root</span>); [protected, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">From CLR </font><br><br></dd>
<script>explorer.outline.writeEnabled = true;</script>
<dt><span class="decl"><li>RBCell <span class="currsymbol"><a href="http://www.dsource.org/projects/tango/browser/trunk/tango/util/collection/impl/RBCell.d?rev=3791#L739">fixAfterDeletion</a></span>
<script>explorer.outline.addDecl('fixAfterDeletion');</script>(RBCell <span class="funcparam">root</span>); [protected, final]</li></span></dt>
<script>explorer.outline.writeEnabled = false;</script>
<dd>
<font color="black">From CLR </font><br><br></dd></dl></dd></dl></td></tr>
                <tr><td id="docfooter">
                         :: page rendered by CandyDoc. Generated by <a href="http://code.google.com/p/dil">dil</a> on Sat Aug  2 16:08:32 2008.
                </td></tr>
        </table>
</div>
<script></script>
</body></html>